public class Solution {
    public static void main(String[] args) {

    }
    public int numWays(int n) {
        /*一定要注意边界的输出*/
        if (n < 2) {return 1;
        }

        int n1 = 1, n2 = 1;
        int res = 0;
        for (int i = 2; i < n+1; i++) {
            res = (n1 + n2) % 1000000007;
            n1 = n2;
            n2 = res;
        }
        return res;

    }
}
/*循环求余法：

大数越界： 随着 nn 增大, f(n)f(n) 会超过 Int32 甚至 Int64 的取值范围，导致最终的返回值错误。

求余运算规则： 设正整数 x, y, px,y,p ，求余符号为 \odot⊙ ，则有 (x + y) \odot p = (x \odot p + y \odot p) \odot p(x+y)⊙p=(x⊙p+y⊙p)⊙p 。
解析： 根据以上规则，可推出 f(n) \odot p = [f(n-1) \odot p + f(n-2) \odot p] \odot pf(n)⊙p=[f(n−1)⊙p+f(n−2)⊙p]⊙p ，从而可以在循环过程中每次计算 sum = a + b \odot 1000000007sum=a+b⊙1000000007 ，此操作与最终返回前取余等价。

作者：jyd
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
